1. Field
This application relates to network elements and, more particularly, to a method for performing IPv6 longest prefix match lookup.
2. Description of the Related Art
Data communication networks may include various switches, nodes, routers, and other devices coupled to and configured to pass data to one another. These devices will be referred to herein as “network elements”. Data is communicated through the data communication network by passing protocol data units, such as frames, packets, cells, or segments, between the network elements by utilizing one or more communication links. A particular protocol data unit may be handled by multiple network elements and cross multiple communication links as it travels between its source and its destination over the network.
Network elements are designed to handle packets of data efficiently, to minimize the amount of delay associated with transmission of the data on the network. Conventionally, this is implemented by using hardware in a data plane of the network element to forward packets of data, while using software in a control plane of the network element to configure the network element to cooperate with other network elements on the network. For example, a network element may include a routing process, which runs in the control plane, that enables the network element to have a synchronized view of the network topology so that the network element is able to forward packets of data across the network toward its intended destination. Multiple processes may be running in the control plane to enable the network element to interact with other network elements on the network and forward data packets on the network.
The applications running in the control plane make decisions about how particular types of traffic should be handled by the network element to allow packets of data to be properly forwarded on the network. As these decisions are made, the control plane programs the hardware in the dataplane to enable the dataplane to be adjusted to properly handle traffic as it is received. The data plane includes ASICs, FPGAs, and other hardware elements designed to receive packets of data, perform lookup operations on specified fields of packet headers, and make forwarding decisions as to how the packet should be transmitted on the network. Lookup operations are typically implemented using tables and registers containing entries populated by the control plane.
One way to address packets of data to enable the packets to be correctly routed through the network is to add an Internet Protocol (IP) header containing an IP address to the packet. When a router receives a packet, it will perform a search in a forwarding table to determine which forwarding rule is to be applied to a packet having the IP address contained in the packet. Since forwarding rules may apply to ranges of IP addresses, not all of the bits of the IP address may be relevant when making a forwarding decision. For example, a given range of IP addresses may be commonly located within a particular sub-network area, such that all traffic addressed to an IP address within the range of IP addresses should be commonly forwarded by a router toward the subnet. In this situation, the less significant bits of the IP address are not relevant to the forwarding decision and, hence, the router may make a forwarding decision by looking only at the more significant bits of the IP address.
An IP address may therefore be viewed as having an address and a prefix length, e.g. address/16 would indicate that the prefix is 16 bits long such that only the 16 most significant bits of the address have forwarding significance. The prefix thus specifies a range of IP addresses since all IP addresses with the same prefix will be forwarded according to the forwarding rule associated with the prefix. For example, a /16 bit prefix would represent a range of 64K IP addresses.
Since it is possible to have sub-ranges associated with different forwarding operations, a router will commonly implement a forwarding decision by looking for the longest prefix of the IP address which matches a routing entry in the forwarding table. This allows more specific routing information to take precedence over more general routing information. For example, a router may have information that packets matching a particular /16 prefix should be forwarded toward a particular destination, but that a sub-range matching a particular /24 prefix should be forwarded to a different destination. Accordingly, when a router receives a packet, it performs a lookup operation to determine the longest prefix in its forwarding tables that matches the IP address contained in the packet. A lookup of this nature is referred to as Longest Prefix Match (LPM).
There are two common methods to implement hardware-based LPM lookup. The first method uses the Ternary Content Addressable Memory (TCAM). A TCAM is a fully-associative memory that can store 0, 1 and don't care bits. In a single clock cycle, a TCAM will find all addresses where information is stored matching the input value. To use a TCAM to implement a longest prefix match, an IP address is input to the TCAM and all prefixes matching the IP address are located. The longest prefix is thus selected. Using TCAM is very fast, since it is able to search all stored prefixes in parallel. However, TCAM consumes a lot of power as compared to other forms of memory, exhibits poor scalability, and is more expensive than other memory technologies.
The second method of implementing an LPM search is based on a multi-bit trie representation of the prefix table. In a multibit trie, one or more bits of a value to be found are scanned in a fixed or variable strides to direct the branching of the children. The issue with this method is its lookup latency since all memory accesses to traverse the tree are sequential. Although latency may be reduced by using higher cost Synchronous Random Access Memory, latency gets worse when lower cost DDR2/3/4 SDRAM memory is used.
There are two versions of the IP protocol, IPv4 and IPv6. IPv4 addresses have 32 bits, which causes many routes to be crowded together such that unused IP addresses may be scarce. Existing Longest Prefix Match algorithms were designed to optimize performance for the 32 bit address space specified by IPv4. IPv6 addresses, by contrast, have 128 bits which enables many more addresses to be available on the network. Unfortunately, using IPv4 algorithms (e.g. pure trie-based or existing TCAM based lookup processes) do not scale well when ported to the 128 bit address space specified by IPv6. Accordingly, it would be advantageous to find a solution for IPv6 which is effective at implementing a longest prefix match search while also exhibiting low latency, at low cost, and which is scalable.